
/*状态：x台阶数，y走法 此时状态满足：子问题最优，而且无后效性。
* 状态转移方程：f[i] = f[i-1]+f[i-2]
* 初始条件：f[1] = 1,f[2] = 2;
* */
public class Solution {
    public static void main(String[] args) {

    }
    public static int getAllPath(int n) {
        // 注意这里代码稍微有点问题：一定要注意数组越界问题：在new一个数组以后直接从3开始是有问题的
        if (n == 1) {
            return 1;
        }else if (n==2) {
            return 2;
        }else {

            int[] f = new int[n + 1];
            f[1] = 1;
            f[2] = 2;
            for (int i = 3; i < n + 1; i++) {
                f[i] = f[i - 1] + f[i - 2];
            }
            return f[n];
        }
    }
}

